#include <iostream>
#include <stdlib.h>
#include <list>
#include <vector>
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include "grafo.h"
#include <algorithm>
#include <map>

void removeEdge(Graph* G,int i,int j,int dual=0){

	if (dual == 1){
		if (j<i) swap(i,j);
	}
	int nodes = G->nodes;
	G->adjacencyMatrix[(i*nodes+j)].id = -1;
}

void putEdge(Graph* G,int i,int j,Edge* e,int dual=0){

	if (dual == 1){
		if (j<i) swap(i,j);
	}
	int nodes = G->nodes;
	G->adjacencyMatrix[(i*nodes+j)] = *e;
	G->adjacencyMatrix[(i*nodes+j)].u = i;
	G->adjacencyMatrix[(i*nodes+j)].v = j;
}
void printGraph(Graph* G){

	for (list<int>::iterator it = G->nodesOrder.begin() ; it != G->nodesOrder.end(); ++it){
		printf(",%d",*it);
	}
	printf("\n");
}

bool existNode(Graph* G,int node){
	for (list<int>::iterator it = G->nodesOrder.begin() ; it != G->nodesOrder.end(); ++it){
		if (  *it == node ){
			return true;
		}
	}
	return false;
}

Edge* getEdge(Graph* G,int i,int j,int dual=0){
	if (dual == 1){
		if (j<i) swap(i,j);
	}
	int nodes = G->nodes;
	if (G->adjacencyMatrix[(i*nodes+j)].id == -1)
		return NULL;
	Edge* p = &G->adjacencyMatrix[(i*nodes+j)];
	return p;
}

Edge* createEdge(int id,int w1,	int w2){
	Edge* e = new Edge;
	e->id = id;
	e->w1 = w1;
	e->w2 = w2;
	return e;
}


void initGraph(Graph* G,int nodesCant){
	G->nodesOrder.resize(0);
	G->nodes = nodesCant;
	G->adjacencyMatrix.resize( nodesCant * nodesCant);
	for (int i=0 ; i< nodesCant * nodesCant; i++){
		G->adjacencyMatrix[i].id = -1;
	}
}

void freeGraph(Graph* G){

}

bool compareEdgesByRandom(Edge* a,Edge* b){
	return (rand()%2 == 0);
}


bool compareEdgesByW2(Edge* a,Edge* b){
	return a->w2 < b->w2;
}
bool compareEdgesByW1(Edge* a,Edge* b){
	return a->w1 < b->w1;
}

void printList(list<Edge*>* L){
	for (list<Edge*>::iterator it = L->begin() ; it != L->end(); ++it){
		printf(" %d,%d,%d,----%d %d|",(*it)->id,(*it)->w1,(*it)->w2,(*it)->u,(*it)->v);
	}
	printf("\n");
}


Result* CalcularCaminoDijkstra(Graph* G,Graph* M, list<Edge*>* S,int s,int e,int K,int origen,int destino){

	list<Edge*>* localS = new list<Edge*>;
	*localS = *S;
	Edge *f,*g,*h,*y;
	Result* r = NULL;
	M->nodesOrder.push_back(e);

	for (int d=0; d < G->nodes; d++){
		removeEdge(M,d,s);
		f = getEdge(G,e,d,1);
		if (d != e && f != NULL && f->id != -1 &&  !existNode(M,d) ){

		 	if(s==0 and f->w1 < K){
				g = createEdge(e,f->w1,f->w2);
				localS->push_back(f);
				putEdge(M,d,s,g);
				continue;
		 	}else{

		 		if( s > 0 ){
		 			g = getEdge(M,e,s-1);
		 		 	if ( g!= NULL && g->w1 + f->w1 < K){
		 		 		localS->push_back(f);
		 		 		h = getEdge(M,d,s-1);
	  					if ( h == NULL ||   g->w1 + f->w1 < h->w1 ||
	  				   	( g->w1+f->w1 == h->w1 &&  g->w2+f->w2 < h->w2 )){
	  				   		y = createEdge(e , g->w1+f->w1, g->w2+f->w2);
							putEdge(M,d,s,y);
	  						continue;
						}
		 			}
		 		}
		 	}

		}
		if (s > 0 ){
			g = getEdge(M,d,s-1);
			if (g != NULL){
				putEdge(M,d,s,g);
			}
		}
	}

        //printAdjacencyMatrix(M);
	localS->sort(compareEdgesByW1);
	if (localS->size() > 0 && s < G->nodes){
		g = localS->front();
		localS->pop_front();
		if ( !existNode(M,g->u)){
			return  CalcularCaminoDijkstra(G,M,localS,s+1,g->u, K,origen, destino);
		}
		if (!existNode(M,g->v)){
				return  CalcularCaminoDijkstra(G,M,localS,s+1,g->v, K, origen,destino);
		}
	}

	s = min(s,G->nodes-1);
	g = getEdge(M,destino,s);
	if (g != NULL && g->id != -1){
		r = new Result;
		r->w1 = g->w1;
		r->w2 = g->w2;
		r->k = K;
		int p = destino;
		// printf("w1 %d w2 %d k %d ->>>>>>>>>> ",r->w1,r->w2,K);
  // 		for (list<int>::iterator it = r->C.begin() ; it != r->C.end(); ++it){
		//  	printf(",%d",*it);
		// }
		// printf("\n");

		r->C.push_front(destino);
		while ( p != origen){
			//me traigo el padre

			if (g->id == origen ) break;
			r->C.push_front(g->id);
			//printf("inserto %d \n",g->id);
			g = getEdge(M,g->id,s);
			if (g == NULL){
				break;
			}

			p = g->id;
		}


		r->C.push_front(origen);
		return r;
	}
	return NULL;
}
Result* CalcularCaminoDijkstraGreedy(Graph* G,Graph* M, list<Edge*>* S,int s,int e,int K,int origen,int destino){

	list<Edge*>* localS = new list<Edge*>;
	*localS = *S;
	Edge *f,*g,*h,*y;
	Result* r = NULL;
	M->nodesOrder.push_back(e);

	for (int d=0; d < G->nodes; d++){
		removeEdge(M,d,s);
		f = getEdge(G,e,d,1);
		if (d != e && f != NULL && f->id != -1 &&  !existNode(M,d) ){

		 	if(s==0 and f->w1 < K){
				g = createEdge(e,f->w1,f->w2);
				localS->push_back(f);
				putEdge(M,d,s,g);
				continue;
		 	}else{

		 		if( s > 0 ){
		 			g = getEdge(M,e,s-1);
		 		 	if ( g!= NULL && g->w1 + f->w1 < K){
		 		 		localS->push_back(f);
		 		 		h = getEdge(M,d,s-1);
	  					if ( h == NULL ||   g->w2 + f->w2 < h->w2 ||
	  				   	( g->w2+f->w2 == h->w2 &&  g->w1+f->w1 < h->w1 )){
	  				   		y = createEdge(e , g->w1+f->w1, g->w2+f->w2);
							putEdge(M,d,s,y);
	  						continue;
						}
		 			}
		 		}
		 	}

		}
		if (s > 0 ){
			g = getEdge(M,d,s-1);
			if (g != NULL){
				putEdge(M,d,s,g);
			}
		}
	}

        //printAdjacencyMatrix(M);
	localS->sort(compareEdgesByW2);
	if (localS->size() > 0 && s < G->nodes){
		g = localS->front();
		localS->pop_front();
		if ( !existNode(M,g->u)){
			return  CalcularCaminoDijkstraGreedy(G,M,localS,s+1,g->u, K,origen, destino);
		}
		if (!existNode(M,g->v)){
				return  CalcularCaminoDijkstraGreedy(G,M,localS,s+1,g->v, K, origen,destino);
		}
	}

	s = min(s,G->nodes-1);
	g = getEdge(M,destino,s);
	if (g != NULL && g->id != -1){
		r = new Result;
		r->w1 = g->w1;
		r->w2 = g->w2;
		r->k = K;
		int p = destino;
		// printf("w1 %d w2 %d k %d ->>>>>>>>>> ",r->w1,r->w2,K);
  // 		for (list<int>::iterator it = r->C.begin() ; it != r->C.end(); ++it){
		//  	printf(",%d",*it);
		// }
		// printf("\n");

		r->C.push_front(destino);
		while ( p != origen){
			//me traigo el padre

			if (g->id == origen ) break;
			r->C.push_front(g->id);
			//printf("inserto %d \n",g->id);
			g = getEdge(M,g->id,s);
			if (g == NULL){
				break;
			}

			p = g->id;
		}


		r->C.push_front(origen);
		return r;
	}
	return NULL;
}

Result* CalcularCaminoDijkstraRandom(Graph* G,Graph* M, list<Edge*>* S,int s,int e,int K,int origen,int destino){

	list<Edge*>* localS = new list<Edge*>;
	*localS = *S;
	Edge *f,*g,*h,*y;
	Result* r = NULL;
	M->nodesOrder.push_back(e);

	for (int d=0; d < G->nodes; d++){
		removeEdge(M,d,s);
		f = getEdge(G,e,d,1);
		if (d != e && f != NULL && f->id != -1 &&  !existNode(M,d) ){

		 	if(s==0 and f->w1 < K){
				g = createEdge(e,f->w1,f->w2);
				localS->push_back(f);
				putEdge(M,d,s,g);
				continue;
		 	}else{

		 		if( s > 0 ){
		 			g = getEdge(M,e,s-1);
		 		 	if ( g!= NULL && g->w1 + f->w1 < K){
		 		 		localS->push_back(f);
		 		 		h = getEdge(M,d,s-1);
	  					if ( h == NULL ||   (g->w2 + f->w2 < h->w2 ||
	  				   		( 0 == (rand() % 2 )) )) {
	  				   		y = createEdge(e , g->w1+f->w1, g->w2+f->w2);
							putEdge(M,d,s,y);
	  						continue;
						}
		 			}
		 		}
		 	}

		}
		if (s > 0 ){
			g = getEdge(M,d,s-1);
			if (g != NULL){
				putEdge(M,d,s,g);
			}
		}
	}

        //printAdjacencyMatrix(M);
	localS->sort(compareEdgesByRandom);
	while (localS->size() > 0 && s < G->nodes){
		g = localS->front();
		localS->pop_front();
		if ( !existNode(M,g->u)){
			return  CalcularCaminoDijkstraRandom(G,M,localS,s+1,g->u, K,origen, destino);
		}
		if (!existNode(M,g->v)){
				return  CalcularCaminoDijkstraRandom(G,M,localS,s+1,g->v, K, origen,destino);
		}
	}

	s = min(s,G->nodes-1);
	g = getEdge(M,destino,s);
	if (g != NULL && g->id != -1){
		r = new Result;
		r->w1 = g->w1;
		r->w2 = g->w2;
		r->k = K;
		int p = destino;
		// printf("w1 %d w2 %d k %d ->>>>>>>>>> ",r->w1,r->w2,K);
  // 		for (list<int>::iterator it = r->C.begin() ; it != r->C.end(); ++it){
		//  	printf(",%d",*it);
		// }
		// printf("\n");

		r->C.push_front(destino);
		while ( p != origen){
			//me traigo el padre

			if (g->id == origen ) break;
			r->C.push_front(g->id);
			//printf("inserto %d \n",g->id);
			g = getEdge(M,g->id,s);
			if (g == NULL){
				break;
			}

			p = g->id;
		}


		r->C.push_front(origen);
		return r;
	}
	return NULL;
}

Result* CalcularCamino(Graph* G,Graph* M, list<Edge*>* S,int s,int e,int K,int origen,int destino){
	//printf("--------------------%d--%d----------%d %d-----------\n",s,e,origen,destino);
	// printAdjacencyMatrix(G);
	list<Edge*>* localS = new list<Edge*>;
	*localS = *S;
	Edge *f,*g,*h,*y;
	Result* r = NULL;
	if (existNode(M,e)){
		return NULL;
	}else{
		// printf("lista entrada  %d :", e);
		// for (list<int>::iterator it = M->nodesOrder.begin() ; it != M->nodesOrder.end(); ++it){
		// 	printf(" %d",*it);
		// }
		// printf("---\n");
	}
	M->nodesOrder.push_back(e);
	for (int d=0; d < G->nodes; d++){
		removeEdge(M,d,s); //limpio el nodo en la columna de la matriz actual.
		f = getEdge(G,e,d,1);
		if (d != e && f != NULL && f->id != -1 &&  !existNode(M,d) ){ //hay doble validacion por manejo de memoria de C++
			// printf(" el nodo no existe  %d, %d, (%d,%d,%d, - %d,%d)\n",e,d,f->id,f->w1,f->w2,f->u,f->v);
		 	if(s==0 and f->w1 < K){
				g = createEdge(e,f->w1,f->w2);
				localS->push_back(f);
				putEdge(M,d,s,g);
				continue;
		 	}else{

		 		if( s > 0 ){
		 			g = getEdge(M,e,s-1);
		 		 	if ( g!= NULL && g->w1 + f->w1 < K){
		 		 		localS->push_back(f);
		 		 		h = getEdge(M,d,s-1);
	  					if ( h == NULL ||   g->w2 + f->w2 < h->w2 ||
	  				   	( g->w2+f->w2 == h->w2 &&  g->w1+f->w1 < h->w1 )){
	  				   		y = createEdge(e , g->w1+f->w1, g->w2+f->w2);
							putEdge(M,d,s,y);
	  						continue;
						}
		 			}
		 		}
		 	}

		}
		if (s > 0 ){
			g = getEdge(M,d,s-1);
			if (g != NULL){
				// printf("copio %d %d\n",s,d);
				putEdge(M,d,s,g); //copio el mejor camino hasta ese nodo por que no mejoro.
			}

		}
	}
	// printf("\n");
	//printAdjacencyMatrix(M);
	// if (s == 5){
	// 	printf("exit aca\n");
	// 	return NULL;
	// }

	localS->sort(compareEdgesByW2);
	//printList(localS);
	int nodesOnCall = M->nodesOrder.size();
	while (localS->size() > 0){
	//	printList(localS);
		g = localS->front();
		// printf("%d,%d,%d----%d,%d\n",g->id,g->w1,g->w2,g->u,g->v);
		localS->pop_front();

		if ( !existNode(M,g->u)){
			r = CalcularCamino(G,M,localS,s+1,g->u, K,origen, destino);
		}else{

			if (!existNode(M,g->v)){
				r = CalcularCamino(G,M,localS,s+1,g->v, K, origen,destino);
			}
		}
		if (NULL != r){
			return r;
		}
		// printf("\n resize -- %d  - %d - " , M->nodesOrder->size(), nodesOnCall);
		// for (list<int>::iterator it = M->nodesOrder->begin() ; it != M->nodesOrder->end(); ++it){
		// 	printf(",%d",*it);
		// }

		M->nodesOrder.resize(nodesOnCall);
		// printf("\n resize despues " );
	/*	for (list<int>::iterator it = M->nodesOrder->begin() ; it != M->nodesOrder->end(); ++it){
			printf(",%d",*it);
		}
		printf("\n"); */
	}
	//printf( "salio del call \n");
	//printAdjacencyMatrix(M);
	g = getEdge(M,destino,s);
	//printf("cant nodes %d %d\n",s , G->nodes );
	if (s == G->nodes-1 && g != NULL){ //reconstruccion del camino.

		r = new Result;
		r->w1 = g->w1;
		r->w2 = g->w2;
		r->k = K;
		int p = destino;
		r->C.push_front(destino);
		while ( p != origen){
			if (g->id == origen ) break;
			r->C.push_front(g->id);
			g = getEdge(M,g->id,s);
			if (g == NULL){
				break;
			}

			p = g->id;
		}
		r->C.push_front(origen);
		return r;
	}
	return NULL;
}

void printAdjacencyMatrix(Graph *G){

	Edge* current;
	for (int i = 0 ; i<= G->nodes; i++){
		for (int j = 0; j<G->nodes; j++){
			if (i == 0){
				printf("|-,%d,-|",j);
			}else{
				current = getEdge(G,i-1,j);
				if (current != NULL and current->id != -1 ){
					printf("|%d,%d,%d|",current->id,current->w1,current->w2);
				}else{
					printf("|-,-,-|");
				}
			}
		}
		printf("\n");
	}
}


void busquedaLocal(Result* R,Graph* G,int cantNodos, int u,int v,int K){
	//OBtengo la sumatoria actual que quiero mejorar

	int sumaActual= R->w2;
	int nueva = -1;
	bool encontre;
	list<int>::iterator itFin = R->C.begin();
	list<int>::iterator itInicio = R->C.begin();
	list<int>::iterator mid;
	list<int>::iterator final = R->C.end();
	final--;

	bool termine = false;
	//Ubico al iterador fin dos nodos mas adelante para empezar
	int SumaLocal = 0;
	int w1 = R->w1;
	list<int> original;
	Edge *e;


	while(!termine){

				//Casos borde
						if(R->C.size()<2){
								break;
						}



						if(itInicio != final){

								original.push_back(*itFin);
								itFin++;
								if(itFin != final){
										original.push_back(*itFin);
										e = getEdge(G,*itInicio,*itFin,1);
										if(e!=NULL){
											SumaLocal += e->w2;
											w1 -= e->w1;

											mid = itFin;
											itFin++;
											original.push_back(*itFin);
											e = getEdge(G,*mid,*itFin,1);
											if(e!=NULL){
												SumaLocal += e->w2;
												w1 -= e->w1;
											}
										}

								}
						}
					//Busco mejor camino

					encontre = buscarNuevo(original,G,cantNodos,K,sumaActual,SumaLocal, w1,nueva);

					//Cambio en la lista si encontre

					if(encontre){
									//Muevo el puntero siempre y cuando pueda
									list<int>:: iterator aux = itInicio;
									aux++;
									R->C.erase(aux);
									aux = itInicio;
									aux++;
									R->C.insert(aux, nueva);

									R->w2 = sumaActual;
									R->w1 = w1;

						} //FIN IF ENCONTRE
							original.clear();
							encontre = false;
							SumaLocal = 0;
							itInicio = itFin;
	//Limpio la lista auxiliar que usa la busqueda de los vecinos

					//adelanto los punteros y reviso si puedo avanzar
					list<int>::iterator aux= itFin;
					aux++;
					if(aux == final || itFin == final) {
							termine = true;
					}

		} //FIN WHILE
}

// buscarNuevo(original,G,cantNodos,K,sumaActual,SumaLocal,nueva);
//original, secuencia orginal de la solucion que se va a mejorar
//sumaActual, suma de orginal
bool buscarNuevo(list<int>& original,Graph* G, int cantNodos, int K, int& sumaActual,int sumaLocal,int& w1Actual,  int& nueva ){

	int sumaMinima = sumaLocal;
	int minimo = -1;
		//resto el w2 de la arista este es el valor del camino u' a v'
	int SumaNueva = sumaActual - sumaLocal;
	int w1 = w1Actual;
	Edge* ein;
	Edge* eout;
	for(int i =0;i<G->nodes;i++){
		//Si los dos tienen un adyacente

					Edge*	e = getEdge(G,original.front(),i,1);
					Edge*	e2 = getEdge(G,original.back(),i,1);

					if(e!= NULL && e2!= NULL){

							if( (e->v == e2->u || e->u == e2->v || e->v == e2->v | e->u == e2->u) &&
											(e->w2 + e2->w2 < sumaMinima && e->w1 + e2->w1 + w1 < K )){
											minimo = i;
											sumaMinima = e->w2 + e2->w2;
											ein = e;
											eout = e2;

							}

					}

	}


	if(minimo !=-1){

		//ACTUALIZO LOS VALORES DE W1 Y W2 EN EL RESULTADO
					nueva = minimo;
					w1Actual +=  ein->w1 + eout->w1 ;
					sumaActual = SumaNueva + ein->w2 + eout->w2 ;
				 return true;
  }
	return false;
}

//Version de busqueda local con 2 Edges para no complicar

void busquedaGrasp(Graph* G,int cantNodos,vector< vector<int> > v ,int origen,int destino,int K){

 	list<Result> Rs;

 	map<int,int > mejorResultado;
 	map<char,int>::iterator it;
 	Result* R;
 	list<Edge*> S;
	Edge *e = new Edge;

 	int i =0;
	for (vector< vector<int> >::iterator it = v.begin() ; it != v.end(); ++it){
		e->id  = i;
		e->w1 = (*it)[2];
		e->w2 = (*it)[3];
		putEdge(G,(*it)[0]-1,(*it)[1]-1,e,1);
		i++;
	}
	Graph *M = new Graph;
	int terminar = 0;
	int sinResultado  =0;
	int mejorW2  = INT_MAX;
	int mejorW2Index;
	int mejorW2Repeat;
	int noMejorResult=0;
	while (!terminar){
		S.resize(0);
		initGraph(M,cantNodos);
		R = CalcularCaminoDijkstraRandom(G,M,&S,0,origen,K,origen,destino);
		if (R != NULL){
			// printf("------------------\n");
			// printf("%d %d %d",R->w1,R->w2,R->k);
			// for (list<int>::iterator it = R->C.begin() ; it != R->C.end(); ++it){
			// 	printf(" %d",*it+1);
			// }
			// printf("\n");

			busquedaLocal(R,G,cantNodos, origen, destino, K);
			if (R->w2 == mejorW2){
				mejorW2Repeat++;
			}else{
				if (R->w2<mejorW2){
//					printf("entro aca");
					mejorW2Repeat = 0;
					noMejorResult =0;
					mejorW2 = R->w2;
					Rs.push_front(*R);
				}else{
					noMejorResult++;
				}
			}
			if (mejorW2Repeat > 10) terminar = 1 ;
			if (noMejorResult > 10) terminar = 1 ;
			sinResultado = 0;
		}else{
			sinResultado ++;
			if(sinResultado >10)
				terminar = 1;

		}
//		printf("- mejorW2Repeat %d noMejorResult %d sinResultado %d \n", mejorW2Repeat,noMejorResult, sinResultado);
	}

	R = &Rs.front();
	/*printf("%d %d %d",R->w1,R->w2,R->k);
	for (list<int>::iterator it = R->C.begin() ; it != R->C.end(); ++it){
		printf(" %d",*it+1);
	}
	printf("\n");*/

}
